package com.company.algo.stack.monotonicStack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/
 *  84. 柱状图中最大的矩形
 *  和接雨水类似
 *  1.先通过暴力找到规律
 *  2.然后考虑合理的数据结构用空间换时间
 */
public class largestRectangleInHistogram {
    //暴力+贪心，枚举所有高度，并通过双指针扩散找到不低于当前高度的柱子，从而得到该高度下的宽度
    //O(N^2)
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int ans = 0;
        for(int i = 0; i<n; i++){
            int h = heights[i];
            int left = i,right = i;
            while(left>=0 && heights[left] >= h) left--;
            while(right<n && heights[right] >= h) right++;
            ans = Math.max(ans, (right-left-1)*h);
        }
        return ans;
    }

    //利用单调栈空间换时间O(N)
    public int largestRectangleArea1(int[] heights){
        int n = heights.length;
        int maxArea = 0;
        Deque<Integer> st = new LinkedList<>();
        //头尾增加两个哨兵，高度为0
        int[] newHeights = new int[n+2];
        System.arraycopy(heights, 0, newHeights, 1, n);
        n +=2;
        heights = newHeights;
        st.push(0);
        for(int i = 1 ; i < n; i++){
            if(heights[i] > heights[st.peek()]){
                st.push(i);
            }else if(heights[i] == heights[st.peek()]){
                st.pop();
                st.push(i);
            }else{
                while(!st.isEmpty() && heights[i] < heights[st.peek()]){
                    int mid = st.pop();
                    int left = st.peek();
                    int right = i;
                    int w = right - left - 1;
                    int h = heights[mid];
                    maxArea = Math.max(maxArea, w*h);
                }
                st.push(i);
            }
        }
        return maxArea;
    }

    public int largestRectangleArea2(int[] heights){
        int len = heights.length;
        if (len == 0) return 0;
        if (len == 1) return heights[0];

        int area = 0;
        int[] newHeights = new int[len+2];      //头尾增加两个哨兵，高度为0
        System.arraycopy(heights, 0, newHeights, 1, len);
        len +=2;
        heights = newHeights;
        Deque<Integer> stack = new ArrayDeque<>();
        //增加头哨兵
        stack.addLast(0);
        for (int i = 1; i < len; i++) { //i从1开始，stack不会为空
            while (heights[stack.peekLast()] > heights[i]){
                int h = heights[stack.pollLast()];
                int width = i - stack.peekLast() - 1;
                area = Math.max(area, width*h);
            }
            stack.addLast(i);
        }
        return area;
    }

    public static void main(String[] args) {
        largestRectangleInHistogram Main = new largestRectangleInHistogram();
        int[] heights = {3,5,2,1,4};
        System.out.println(Main.largestRectangleArea1(heights));
    }
}
